package com.mingweicai.intergration.lc;

import java.util.ArrayList;
import java.util.List;

class TreeNode {
  int val = 0;
  TreeNode left = null;
  TreeNode right = null;

  public TreeNode(int val) {
    this.val = val;

  }
}

public class FindPath {

  public static void main(String args[]){

    TreeNode root = new TreeNode(10);
    TreeNode node1 = new TreeNode(5);
    TreeNode node2 = new TreeNode(12);
    TreeNode node3 = new TreeNode(4);
    TreeNode node4 = new TreeNode(7);

    root.left = node1;
    root.right = node2;
    node1.left = node3;
    node1.right = node4;

    List<TreeNode> path = new ArrayList<>();
    List<List<TreeNode>> ans = new ArrayList<>();

    findPath(root, 22, path, ans);
  }

  public static void findPath(TreeNode root, int k,
      List<TreeNode> path, List<List<TreeNode>> ans){

    if(root == null){
      return;
    }
    // already leaf
    if(root.left == null && root.right == null){
      if(k == root.val){
        printPath(path, root);
      }
      return;
    }
    if(!(root.val > k)){
      path.add(root);
      findPath(root.left,k - root.val, path, ans);
      findPath(root.right,k - root.val, path, ans);
      path.remove(path.size() - 1);
    }
  }

  public static void printPath(List<TreeNode> path, TreeNode tail){
    for(TreeNode treeNode: path){
      System.out.print(treeNode.val + ", ");
    }
    System.out.println(tail.val);
  }
}
